class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        m, n = len(board), len(board[0])
        cnt = Counter(c for row in board for c in row)
        if not cnt >= Counter(word):
            return False
        '''
        如果 word 的某个字母的出现次数，比 board 中的这个字母的出现次数还要多，可以直接返回 false。
        '''
        if cnt[word[-1]] < cnt[word[0]]:
            word = word[::-1]
        '''
        设 word 的第一个字母在 board 中出现了 x 次，word 的最后一个字母在 board 中出现了 y 次。

        如果 y<x，我们可以把 word 反转，相当于从 word 的最后一个字母开始搜索，这样更容易在一开始满足 board[i][j] != word[k]，不会往下递归，递归的总次数更少。
        '''
        def dfs(i, j, k):
            if board[i][j] != word[k]:
                return False
            if k == len(word) - 1:
                return True
            board[i][j] = ''
            for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):
                if 0 <= x <m and 0<=y<n and dfs(x, y, k + 1):
                    return True
            board[i][j] = word[k] # 恢复现场
            return False
        return any(dfs(i, j, 0) for i in range(m) for j in range(n))